class Solution:
    def checkRecord(self, n: int) -> int:
        mod = 1000000007
        f = [[0] * 3 for _ in range(2)]
        f[0][0] = 1
        for _ in range(n):
            p = [[0] * 3 for _ in range(2)]
            for i in range(2):
                for j in range(3):
                    p[i][0] += f[i][j]  # 'P'
                    if j < 2:
                        p[i][j + 1] += f[i][j]  #'L'
                    if i == 0:
                        p[i + 1][0] += f[i][j]  #'A'
                    p[i][j] %= mod
            f = p
        return sum(map(sum, f)) % mod


s = Solution()
print(s.checkRecord(1))
print(s.checkRecord(2))
print(s.checkRecord(10101))

# f = [[0] * 3 for _ in range(2)]
# for i in range(2):
#     for j in range(3):
#         f[i][j] = i * 3 + j
# for r in f:
#     print(r)
# print(sum(map(sum, f)))
